#include "wx/wxprec.h"
#include <ctype.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>

#define EXTRA_ALLOC       (19 - nLen % 16)

const size_t wxStringBase::npos = ( size_t ) - 1;

static const struct {
  wxStringData data;
  wxChar dummy;
} g_strEmpty = { {-1, 0, 0}, wxT( '\0' ) };

extern const wxChar *wxEmptyString = &g_strEmpty.dummy;

#include <iostream>

wxSTD ostream& operator<<( wxSTD ostream& os, const wxString& str ) {
  os << str.c_str();
  return os;
}

#ifdef  WXSTRING_STATISTICS
#error mmmmm
class Averager {
  public:
    Averager( const wxChar *sz ) { m_sz = sz; m_nTotal = m_nCount = 0; }
    ~Averager() { wxPrintf( "wxString: average %s = %f\n", m_sz, ( ( float )m_nTotal ) / m_nCount ); }

    void Add( size_t n ) { m_nTotal += n; m_nCount++; }

  private:
    size_t m_nCount, m_nTotal;
    const wxChar *m_sz;
} g_averageLength( "allocation size" ),
g_averageSummandLength( "summand length" ),
g_averageConcatHit( "hit probability in concat" ),
g_averageInitialLength( "initial string length" );

#define STATISTICS_ADD(av, val) g_average##av.Add(val)
#else
#define STATISTICS_ADD(av, val)
#endif // WXSTRING_STATISTICS

#if !wxUSE_STL

void wxStringBase::InitWith( const wxChar *psz, size_t nPos, size_t nLength ) {
  Init();
  // if the length is not given, assume the string to be NUL terminated
  if( nLength == npos ) {
    wxASSERT_MSG( nPos <= wxStrlen( psz ), _T( "索引越界" ) );
    nLength = wxStrlen( psz + nPos );
  }
  STATISTICS_ADD( InitialLength, nLength );
  if( nLength > 0 ) {
    // trailing '\0' is written in AllocBuffer()
    if( !AllocBuffer( nLength ) ) {
      wxFAIL_MSG( _T( "out of memory in wxStringBase::InitWith" ) );
      return;
    }
    wxTmemcpy( m_pchData, psz + nPos, nLength );
  }
}

// poor man's iterators are "void *" pointers
wxStringBase::wxStringBase( const void *pStart, const void *pEnd ) {
  if( pEnd >= pStart ) {
    InitWith( ( const wxChar * )pStart, 0,
              ( const wxChar * )pEnd - ( const wxChar * )pStart );
  } else {
    wxFAIL_MSG( _T( "pStart不在pEnd之前" ) );
    Init();
  }
}

wxStringBase::wxStringBase( size_type n, wxChar ch ) {
  Init();
  append( n, ch );
}

// ---------------------------------------------------------------------------
// memory allocation
// ---------------------------------------------------------------------------

// allocates memory needed to store a C string of length nLen
bool wxStringBase::AllocBuffer( size_t nLen ) {
  // allocating 0 sized buffer doesn't make sense, all empty strings should
  // reuse g_strEmpty
  wxASSERT( nLen >  0 );
  // make sure that we don't overflow
  wxCHECK( nLen < ( INT_MAX / sizeof( wxChar ) ) -
           ( sizeof( wxStringData ) + EXTRA_ALLOC + 1 ), false );
  STATISTICS_ADD( Length, nLen );
  // allocate memory:
  // 1) one extra character for '\0' termination
  // 2) sizeof(wxStringData) for housekeeping info
  wxStringData* pData = ( wxStringData* )
                        malloc( sizeof( wxStringData ) + ( nLen + EXTRA_ALLOC + 1 ) * sizeof( wxChar ) );
  if( pData == NULL ) {
    // allocation failures are handled by the caller
    return false;
  }
  pData->nRefs        = 1;
  pData->nDataLength  = nLen;
  pData->nAllocLength = nLen + EXTRA_ALLOC;
  m_pchData           = pData->data();  // data starts after wxStringData
  m_pchData[nLen]     = wxT( '\0' );
  return true;
}

// must be called before changing this string
bool wxStringBase::CopyBeforeWrite() {
  wxStringData* pData = GetStringData();
  if( pData->IsShared() ) {
    pData->Unlock();                // memory not freed because shared
    size_t nLen = pData->nDataLength;
    if( !AllocBuffer( nLen ) ) {
      // allocation failures are handled by the caller
      return false;
    }
    wxTmemcpy( m_pchData, pData->data(), nLen );
  }
  wxASSERT( !GetStringData()->IsShared() );  // we must be the only owner
  return true;
}

// must be called before replacing contents of this string
bool wxStringBase::AllocBeforeWrite( size_t nLen ) {
  wxASSERT( nLen != 0 );  // doesn't make any sense
  // must not share string and must have enough space
  wxStringData* pData = GetStringData();
  if( pData->IsShared() || pData->IsEmpty() ) {
    // can't work with old buffer, get new one
    pData->Unlock();
    if( !AllocBuffer( nLen ) ) {
      // allocation failures are handled by the caller
      return false;
    }
  } else {
    if( nLen > pData->nAllocLength ) {
      // realloc the buffer instead of calling malloc() again, this is more
      // efficient
      STATISTICS_ADD( Length, nLen );
      nLen += EXTRA_ALLOC;
      pData = ( wxStringData* )
              realloc( pData, sizeof( wxStringData ) + ( nLen + 1 ) * sizeof( wxChar ) );
      if( pData == NULL ) {
        // allocation failures are handled by the caller
        // keep previous data since reallocation failed
        return false;
      }
      pData->nAllocLength = nLen;
      m_pchData = pData->data();
    }
  }
  wxASSERT( !GetStringData()->IsShared() );  // we must be the only owner
  // it doesn't really matter what the string length is as it's going to be
  // overwritten later but, for extra safety, set it to 0 for now as we may
  // have some junk in m_pchData
  GetStringData()->nDataLength = 0;
  return true;
}

wxStringBase& wxStringBase::append( size_t n, wxChar ch ) {
  size_type len = length();
  if( !Alloc( len + n ) || !CopyBeforeWrite() ) {
    wxFAIL_MSG( _T( "out of memory in wxStringBase::append" ) );
  }
  GetStringData()->nDataLength = len + n;
  m_pchData[len + n] = '\0';
  for( size_t i = 0; i < n; ++i ) {
    m_pchData[len + i] = ch;
  }
  return *this;
}

void wxStringBase::resize( size_t nSize, wxChar ch ) {
  size_t len = length();
  if( nSize < len ) {
    erase( begin() + nSize, end() );
  } else if( nSize > len ) {
    append( nSize - len, ch );
  }
  //else: we have exactly the specified length, nothing to do
}

// allocate enough memory for nLen characters
bool wxStringBase::Alloc( size_t nLen ) {
  wxStringData *pData = GetStringData();
  if( pData->nAllocLength <= nLen ) {
    if( pData->IsEmpty() ) {
      nLen += EXTRA_ALLOC;
      pData = ( wxStringData * )
              malloc( sizeof( wxStringData ) + ( nLen + 1 ) * sizeof( wxChar ) );
      if( pData == NULL ) {
        // allocation failure handled by caller
        return false;
      }
      pData->nRefs = 1;
      pData->nDataLength = 0;
      pData->nAllocLength = nLen;
      m_pchData = pData->data();  // data starts after wxStringData
      m_pchData[0u] = wxT( '\0' );
    } else if( pData->IsShared() ) {
      pData->Unlock();                // memory not freed because shared
      size_t nOldLen = pData->nDataLength;
      if( !AllocBuffer( nLen ) ) {
        // allocation failure handled by caller
        return false;
      }
      // +1 to copy the terminator, too
      memcpy( m_pchData, pData->data(), ( nOldLen + 1 )*sizeof( wxChar ) );
      GetStringData()->nDataLength = nOldLen;
    } else {
      nLen += EXTRA_ALLOC;
      pData = ( wxStringData * )
              realloc( pData, sizeof( wxStringData ) + ( nLen + 1 ) * sizeof( wxChar ) );
      if( pData == NULL ) {
        // allocation failure handled by caller
        // keep previous data since reallocation failed
        return false;
      }
      // it's not important if the pointer changed or not (the check for this
      // is not faster than assigning to m_pchData in all cases)
      pData->nAllocLength = nLen;
      m_pchData = pData->data();
    }
  }
  //else: we've already got enough
  return true;
}

wxStringBase::iterator wxStringBase::begin() {
  if( length() > 0 ) {
    CopyBeforeWrite();
  }
  return m_pchData;
}

wxStringBase::iterator wxStringBase::end() {
  if( length() > 0 ) {
    CopyBeforeWrite();
  }
  return m_pchData + length();
}

wxStringBase::iterator wxStringBase::erase( iterator it ) {
  size_type idx = it - begin();
  erase( idx, 1 );
  return begin() + idx;
}

wxStringBase& wxStringBase::erase( size_t nStart, size_t nLen ) {
  wxASSERT( nStart <= length() );
  size_t strLen = length() - nStart;
  // delete nLen or up to the end of the string characters
  nLen = strLen < nLen ? strLen : nLen;
  wxString strTmp( c_str(), nStart );
  strTmp.append( c_str() + nStart + nLen, length() - nStart - nLen );
  swap( strTmp );
  return *this;
}

wxStringBase& wxStringBase::insert( size_t nPos, const wxChar *sz, size_t n ) {
  wxASSERT( nPos <= length() );
  if( n == npos ) {
    n = wxStrlen( sz );
  }
  if( n == 0 ) {
    return *this;
  }
  if( !Alloc( length() + n ) || !CopyBeforeWrite() ) {
    wxFAIL_MSG( _T( "out of memory in wxStringBase::insert" ) );
  }
  memmove( m_pchData + nPos + n, m_pchData + nPos,
           ( length() - nPos ) * sizeof( wxChar ) );
  memcpy( m_pchData + nPos, sz, n * sizeof( wxChar ) );
  GetStringData()->nDataLength = length() + n;
  m_pchData[length()] = '\0';
  return *this;
}

void wxStringBase::swap( wxStringBase& str ) {
  wxChar* tmp = str.m_pchData;
  str.m_pchData = m_pchData;
  m_pchData = tmp;
}

size_t wxStringBase::find( const wxStringBase& str, size_t nStart ) const {
  // deal with the special case of empty string first
  const size_t nLen = length();
  const size_t nLenOther = str.length();
  if( !nLenOther ) {
    // empty string is a substring of anything
    return 0;
  }
  if( !nLen ) {
    // the other string is non empty so can't be our substring
    return npos;
  }
  wxASSERT( str.GetStringData()->IsValid() );
  wxASSERT( nStart <= nLen );
  const wxChar * const other = str.c_str();
  // anchor
  const wxChar* p = ( const wxChar* )wxTmemchr( c_str() + nStart,
                    *other,
                    nLen - nStart );
  if( !p ) {
    return npos;
  }
  while( p - c_str() + nLenOther <= nLen && wxTmemcmp( p, other, nLenOther ) ) {
    p++;
    // anchor again
    p = ( const wxChar* )wxTmemchr( p, *other, nLen - ( p - c_str() ) );
    if( !p ) {
      return npos;
    }
  }
  return p - c_str() + nLenOther <= nLen ? p - c_str() : npos;
}

size_t wxStringBase::find( const wxChar* sz, size_t nStart, size_t n ) const {
  return find( wxStringBase( sz, n ), nStart );
}

size_t wxStringBase::find( wxChar ch, size_t nStart ) const {
  wxASSERT( nStart <= length() );
  const wxChar *p = ( const wxChar* )wxTmemchr( c_str() + nStart, ch, length() - nStart );
  return p == NULL ? npos : p - c_str();
}

size_t wxStringBase::rfind( const wxStringBase& str, size_t nStart ) const {
  wxASSERT( str.GetStringData()->IsValid() );
  wxASSERT( nStart == npos || nStart <= length() );
  if( length() >= str.length() ) {
    // avoids a corner case later
    if( length() == 0 && str.length() == 0 ) {
      return 0;
    }
    // "top" is the point where search starts from
    size_t top = length() - str.length();
    if( nStart == npos ) {
      nStart = length() - 1;
    }
    if( nStart < top ) {
      top = nStart;
    }
    const wxChar *cursor = c_str() + top;
    do {
      if( wxTmemcmp( cursor, str.c_str(),
                     str.length() ) == 0 ) {
        return cursor - c_str();
      }
    } while( cursor-- > c_str() );
  }
  return npos;
}

size_t wxStringBase::rfind( const wxChar* sz, size_t nStart, size_t n ) const {
  return rfind( wxStringBase( sz, n ), nStart );
}

size_t wxStringBase::rfind( wxChar ch, size_t nStart ) const {
  if( nStart == npos ) {
    nStart = length();
  } else
  { wxASSERT( nStart <= length() ); }
  const wxChar *actual;
  for( actual = c_str() + ( nStart == npos ? length() : nStart + 1 );
       actual > c_str(); --actual ) {
    if( *( actual - 1 ) == ch ) {
      return ( actual - 1 ) - c_str();
    }
  }
  return npos;
}

size_t wxStringBase::find_first_of( const wxChar* sz, size_t nStart ) const {
  wxASSERT( nStart <= length() );
  size_t len = wxStrlen( sz );
  size_t i;
  for( i = nStart; i < this->length(); ++i ) {
    if( wxTmemchr( sz, *( c_str() + i ), len ) ) {
      break;
    }
  }
  if( i == this->length() ) {
    return npos;
  } else
  { return i; }
}

size_t wxStringBase::find_first_of( const wxChar* sz, size_t nStart,
                                    size_t n ) const {
  return find_first_of( wxStringBase( sz, n ), nStart );
}

size_t wxStringBase::find_last_of( const wxChar* sz, size_t nStart ) const {
  if( nStart == npos ) {
    nStart = length() - 1;
  } else {
    wxASSERT_MSG( nStart <= length(),
                  _T( "invalid index in find_last_of()" ) );
  }
  size_t len = wxStrlen( sz );
  for( const wxChar *p = c_str() + nStart; p >= c_str(); --p ) {
    if( wxTmemchr( sz, *p, len ) ) {
      return p - c_str();
    }
  }
  return npos;
}

size_t wxStringBase::find_last_of( const wxChar* sz, size_t nStart,
                                   size_t n ) const {
  return find_last_of( wxStringBase( sz, n ), nStart );
}

size_t wxStringBase::find_first_not_of( const wxChar* sz, size_t nStart ) const {
  if( nStart == npos ) {
    nStart = length();
  } else
  { wxASSERT( nStart <= length() ); }
  size_t len = wxStrlen( sz );
  size_t i;
  for( i = nStart; i < this->length(); ++i ) {
    if( !wxTmemchr( sz, *( c_str() + i ), len ) ) {
      break;
    }
  }
  if( i == this->length() ) {
    return npos;
  } else
  { return i; }
}

size_t wxStringBase::find_first_not_of( const wxChar* sz, size_t nStart,
                                        size_t n ) const {
  return find_first_not_of( wxStringBase( sz, n ), nStart );
}

size_t wxStringBase::find_first_not_of( wxChar ch, size_t nStart ) const {
  wxASSERT( nStart <= length() );
  for( const wxChar *p = c_str() + nStart; *p; p++ ) {
    if( *p != ch ) {
      return p - c_str();
    }
  }
  return npos;
}

size_t wxStringBase::find_last_not_of( const wxChar* sz, size_t nStart ) const {
  if( nStart == npos ) {
    nStart = length() - 1;
  } else
  { wxASSERT( nStart <= length() ); }
  size_t len = wxStrlen( sz );
  for( const wxChar *p = c_str() + nStart; p >= c_str(); --p ) {
    if( !wxTmemchr( sz, *p, len ) ) {
      return p - c_str();
    }
  }
  return npos;
}

size_t wxStringBase::find_last_not_of( const wxChar* sz, size_t nStart,
                                       size_t n ) const {
  return find_last_not_of( wxStringBase( sz, n ), nStart );
}

size_t wxStringBase::find_last_not_of( wxChar ch, size_t nStart ) const {
  if( nStart == npos ) {
    nStart = length() - 1;
  } else
  { wxASSERT( nStart <= length() ); }
  for( const wxChar *p = c_str() + nStart; p >= c_str(); --p ) {
    if( *p != ch ) {
      return p - c_str();
    }
  }
  return npos;
}

wxStringBase& wxStringBase::replace( size_t nStart, size_t nLen,
                                     const wxChar *sz ) {
  wxASSERT_MSG( nStart <= length(), _T( "index out of bounds in wxStringBase::replace" ) );
  size_t strLen = length() - nStart;
  nLen = strLen < nLen ? strLen : nLen;
  wxStringBase strTmp;
  strTmp.reserve( length() );
  for( size_t i1 = 0; i1 < nStart; ++i1 ) {
    strTmp.append( 1, this->c_str()[i1] );
  }
  strTmp.append( sz );
  for( size_t i2 = nStart + nLen; i2 < length(); ++i2 ) {
    strTmp.append( 1, this->c_str()[i2] );
  }
  swap( strTmp );
  return *this;
}

wxStringBase& wxStringBase::replace( size_t nStart, size_t nLen, size_t nCount, wxChar ch ) {
  return replace( nStart, nLen, wxStringBase( nCount, ch ).c_str() );
}

wxStringBase& wxStringBase::replace( size_t nStart, size_t nLen, const wxStringBase& str, size_t nStart2, size_t nLen2 ) {
  return replace( nStart, nLen, str.substr( nStart2, nLen2 ) );
}

wxStringBase& wxStringBase::replace( size_t nStart, size_t nLen, const wxChar* sz, size_t nCount ) {
  return replace( nStart, nLen, wxStringBase( sz, nCount ).c_str() );
}

wxStringBase wxStringBase::substr( size_t nStart, size_t nLen ) const {
  if( nLen == npos ) {
    nLen = length() - nStart;
  }
  return wxStringBase( *this, nStart, nLen );
}

wxStringBase& wxStringBase::operator=( const wxStringBase& stringSrc ) {
  wxASSERT( stringSrc.GetStringData()->IsValid() );
  if( m_pchData != stringSrc.m_pchData ) {
    if( stringSrc.GetStringData()->IsEmpty() ) {
      Reinit();
    } else {
      GetStringData()->Unlock();
      m_pchData = stringSrc.m_pchData;
      GetStringData()->Lock();
    }
  }
  return *this;
}

wxStringBase& wxStringBase::operator=( wxChar ch ) {
  if( !AssignCopy( 1, &ch ) ) {
    wxFAIL_MSG( _T( "out of memory in wxStringBase::operator=(wxChar)" ) );
  }
  return *this;
}

wxStringBase& wxStringBase::operator=( const wxChar *psz ) {
  if( !AssignCopy( wxStrlen( psz ), psz ) ) {
    wxFAIL_MSG( _T( "out of memory in wxStringBase::operator=(const wxChar *)" ) );
  }
  return *this;
}

bool wxStringBase::AssignCopy( size_t nSrcLen, const wxChar *pszSrcData ) {
  if( nSrcLen == 0 ) {
    Reinit();
  } else {
    if( !AllocBeforeWrite( nSrcLen ) ) {
      return false;
    }
    memmove( m_pchData, pszSrcData, nSrcLen * sizeof( wxChar ) );
    GetStringData()->nDataLength = nSrcLen;
    m_pchData[nSrcLen] = wxT( '\0' );
  }
  return true;
}

bool wxStringBase::ConcatSelf( size_t nSrcLen, const wxChar *pszSrcData, size_t nMaxLen ) {
  STATISTICS_ADD( SummandLength, nSrcLen );
  nSrcLen = nSrcLen < nMaxLen ? nSrcLen : nMaxLen;
  if( nSrcLen > 0 ) {
    wxStringData *pData = GetStringData();
    size_t nLen = pData->nDataLength;
    size_t nNewLen = nLen + nSrcLen;
    if( pszSrcData >= m_pchData && pszSrcData < m_pchData + nLen ) {
      wxStringBase tmp( pszSrcData, nSrcLen );
      return ConcatSelf( nSrcLen, tmp.m_pchData, nSrcLen );
    }
    if( pData->IsShared() ) {
      STATISTICS_ADD( ConcatHit, 0 );
      wxStringData* pOldData = GetStringData();
      if( !AllocBuffer( nNewLen ) ) {
        return false;
      }
      memcpy( m_pchData, pOldData->data(), nLen * sizeof( wxChar ) );
      pOldData->Unlock();
    } else if( nNewLen > pData->nAllocLength ) {
      STATISTICS_ADD( ConcatHit, 0 );
      reserve( nNewLen );
      if( capacity() < nNewLen ) {
        return false;
      }
    } else {
      STATISTICS_ADD( ConcatHit, 1 );
    }
    wxASSERT( nNewLen <= GetStringData()->nAllocLength );
    memcpy( m_pchData + nLen, pszSrcData, nSrcLen * sizeof( wxChar ) );
    m_pchData[nNewLen] = wxT( '\0' );        // put terminating '\0'
    GetStringData()->nDataLength = nNewLen; // and fix the length
  }
  return true;
}

bool wxStringBase::AllocCopy( wxString& dest, int nCopyLen, int nCopyIndex ) const {
  if( nCopyLen == 0 ) {
    dest.Init();
  } else {
    if( !dest.AllocBuffer( nCopyLen ) ) {
      return false;
    }
    memcpy( dest.m_pchData, m_pchData + nCopyIndex, nCopyLen * sizeof( wxChar ) );
  }
  return true;
}

#endif

#if !wxUSE_STL || !defined(HAVE_STD_STRING_COMPARE)

#if !wxUSE_STL
#define STRINGCLASS wxStringBase
#else
#define STRINGCLASS wxString
#endif

static inline int wxDoCmp( const wxChar* s1, size_t l1, const wxChar* s2, size_t l2 ) {
  if( l1 == l2 ) {
    return wxTmemcmp( s1, s2, l1 );
  } else if( l1 < l2 ) {
    int ret = wxTmemcmp( s1, s2, l1 );
    return ret == 0 ? -1 : ret;
  } else {
    int ret = wxTmemcmp( s1, s2, l2 );
    return ret == 0 ? +1 : ret;
  }
}

int STRINGCLASS::compare( const wxStringBase& str ) const {
  return ::wxDoCmp( data(), length(), str.data(), str.length() );
}

int STRINGCLASS::compare( size_t nStart, size_t nLen, const wxStringBase& str ) const {
  wxASSERT( nStart <= length() );
  size_type strLen = length() - nStart;
  nLen = strLen < nLen ? strLen : nLen;
  return ::wxDoCmp( data() + nStart, nLen, str.data(), str.length() );
}

int STRINGCLASS::compare( size_t nStart, size_t nLen, const wxStringBase& str, size_t nStart2, size_t nLen2 ) const {
  wxASSERT( nStart <= length() );
  wxASSERT( nStart2 <= str.length() );
  size_type strLen  = length() - nStart, strLen2 = str.length() - nStart2;
  nLen  = strLen  < nLen  ? strLen  : nLen;
  nLen2 = strLen2 < nLen2 ? strLen2 : nLen2;
  return ::wxDoCmp( data() + nStart, nLen, str.data() + nStart2, nLen2 );
}

int STRINGCLASS::compare( const wxChar* sz ) const {
  size_t nLen = wxStrlen( sz );
  return ::wxDoCmp( data(), length(), sz, nLen );
}

int STRINGCLASS::compare( size_t nStart, size_t nLen,
                          const wxChar* sz, size_t nCount ) const {
  wxASSERT( nStart <= length() );
  size_type strLen = length() - nStart;
  nLen = strLen < nLen ? strLen : nLen;
  if( nCount == npos ) {
    nCount = wxStrlen( sz );
  }
  return ::wxDoCmp( data() + nStart, nLen, sz, nCount );
}

#undef STRINGCLASS

#endif

wxString::wxString( const char *psz, const wxMBConv& conv, size_t nLength ) {
  if( psz && nLength != 0 ) {
    if( nLength == npos ) {
      nLength = wxNO_LEN;
    }
    size_t nLenWide;
    wxWCharBuffer wbuf = conv.cMB2WC( psz, nLength, &nLenWide );
    if( nLenWide ) {
      assign( wbuf, nLenWide );
    }
  }
}

const wxCharBuffer wxString::mb_str( const wxMBConv& conv ) const {
  return conv.cWC2MB( c_str(), length() + 1, NULL );
}

bool wxString::Shrink() {
  wxString tmp( begin(), end() );
  swap( tmp );
  return tmp.length() == length();
}

#if !wxUSE_STL
wxChar *wxString::GetWriteBuf( size_t nLen ) {
  if( !AllocBeforeWrite( nLen ) ) {
    return NULL;
  }
  wxASSERT( GetStringData()->nRefs == 1 );
  GetStringData()->Validate( false );
  return m_pchData;
}

void wxString::UngetWriteBuf() {
  UngetWriteBuf( wxStrlen( m_pchData ) );
}

void wxString::UngetWriteBuf( size_t nLen ) {
  wxStringData * const pData = GetStringData();
  wxASSERT_MSG( nLen < pData->nAllocLength, _T( "buffer overrun" ) );
  pData->data()[nLen] = _T( '\0' );
  pData->nDataLength = nLen;
  pData->Validate( true );
}
#endif // !wxUSE_STL

wxString operator+( const wxString& str1, const wxString& str2 ) {
  #if !wxUSE_STL
  wxASSERT( str1.GetStringData()->IsValid() );
  wxASSERT( str2.GetStringData()->IsValid() );
  #endif
  wxString s = str1;
  s += str2;
  return s;
}

wxString operator+( const wxString& str, wxChar ch ) {
  #if !wxUSE_STL
  wxASSERT( str.GetStringData()->IsValid() );
  #endif
  wxString s = str;
  s += ch;
  return s;
}

wxString operator+( wxChar ch, const wxString& str ) {
  #if !wxUSE_STL
  wxASSERT( str.GetStringData()->IsValid() );
  #endif
  wxString s = ch;
  s += str;
  return s;
}

wxString operator+( const wxString& str, const wxChar *psz ) {
  #if !wxUSE_STL
  wxASSERT( str.GetStringData()->IsValid() );
  #endif
  wxString s;
  if( !s.Alloc( wxStrlen( psz ) + str.length() ) ) {
    wxFAIL_MSG( _T( "out of memory in wxString::operator+" ) );
  }
  s += str;
  s += psz;
  return s;
}

wxString operator+( const wxChar *psz, const wxString& str ) {
  #if !wxUSE_STL
  wxASSERT( str.GetStringData()->IsValid() );
  #endif
  wxString s;
  if( !s.Alloc( wxStrlen( psz ) + str.length() ) ) {
    wxFAIL_MSG( _T( "out of memory in wxString::operator+" ) );
  }
  s = psz;
  s += str;
  return s;
}

int wxString::Cmp( const wxString& s ) const {
  return compare( s );
}

int wxString::Cmp( const wxChar* psz ) const {
  return compare( psz );
}

static inline int wxDoCmpNoCase( const wxChar* s1, size_t l1, const wxChar* s2, size_t l2 ) {
  size_t i;
  if( l1 == l2 ) {
    for( i = 0; i < l1; ++i ) {
      if( wxTolower( s1[i] ) != wxTolower( s2[i] ) ) {
        break;
      }
    }
    return i == l1 ? 0 : wxTolower( s1[i] ) < wxTolower( s2[i] ) ? -1 : 1;
  } else if( l1 < l2 ) {
    for( i = 0; i < l1; ++i ) {
      if( wxTolower( s1[i] ) != wxTolower( s2[i] ) ) {
        break;
      }
    }
    return i == l1 ? -1 : wxTolower( s1[i] ) < wxTolower( s2[i] ) ? -1 : 1;
  } else {
    for( i = 0; i < l2; ++i ) {
      if( wxTolower( s1[i] ) != wxTolower( s2[i] ) ) {
        break;
      }
    }
    return i == l2 ? 1 : wxTolower( s1[i] ) < wxTolower( s2[i] ) ? -1 : 1;
  }
}

int wxString::CmpNoCase( const wxString& s ) const {
  return wxDoCmpNoCase( data(), length(), s.data(), s.length() );
}

int wxString::CmpNoCase( const wxChar* psz ) const {
  int nLen = wxStrlen( psz );
  return wxDoCmpNoCase( data(), length(), psz, nLen );
}

#ifdef __MWERKS__
#ifndef __SCHAR_MAX__
#define __SCHAR_MAX__ 127
#endif
#endif

wxString wxString::FromAscii( const char *ascii ) {
  if( !ascii ) {
    return wxEmptyString;
  }
  size_t len = strlen( ascii );
  wxString res;
  if( len ) {
    wxStringBuffer buf( res, len );
    wchar_t *dest = buf;
    for( ;; ) {
      if( ( *dest++ = ( wchar_t )( unsigned char ) * ascii++ ) == L'\0' ) {
        break;
      }
    }
  }
  return res;
}

wxString wxString::FromAscii( const char ascii ) {
  wxString res;
  res += ( wchar_t )( unsigned char ) ascii;
  return res;
}

const wxCharBuffer wxString::ToAscii() const {
  wxCharBuffer buffer( length() );
  char *dest = buffer.data();
  const wchar_t *pwc = c_str();
  for( ;; ) {
    *dest++ = ( char )( *pwc > SCHAR_MAX ? wxT( '_' ) : *pwc );
    if( !*pwc++ ) {
      break;
    }
  }
  return buffer;
}

wxString wxString::Mid( size_t nFirst, size_t nCount ) const {
  size_t nLen = length();
  if( nCount == npos ) {
    nCount = nLen - nFirst;
  }
  if( nFirst + nCount > nLen ) {
    nCount = nLen - nFirst;
  }
  if( nFirst > nLen ) {
    return wxEmptyString;
  }
  wxString dest( *this, nFirst, nCount );
  if( dest.length() != nCount ) {
    wxFAIL_MSG( _T( "out of memory in wxString::Mid" ) );
  }
  return dest;
}

bool wxString::StartsWith( const wxChar *prefix, wxString *rest ) const {
  wxASSERT_MSG( prefix, _T( "invalid parameter in wxString::StartsWith" ) );
  const wxChar *p = c_str();
  while( *prefix ) {
    if( *prefix++ != *p++ ) {
      return false;
    }
  }
  if( rest ) {
    *rest = p;
  }
  return true;
}

bool wxString::EndsWith( const wxChar *suffix, wxString *rest ) const {
  wxASSERT_MSG( suffix, _T( "invalid parameter in wxString::EndssWith" ) );
  int start = length() - wxStrlen( suffix );
  if( start < 0 || wxStrcmp( c_str() + start, suffix ) != 0 ) {
    return false;
  }
  if( rest ) {
    rest->assign( *this, 0, start );
  }
  return true;
}

wxString wxString::Right( size_t nCount ) const {
  if( nCount > length() ) {
    nCount = length();
  }
  wxString dest( *this, length() - nCount, nCount );
  if( dest.length() != nCount ) {
    wxFAIL_MSG( _T( "out of memory in wxString::Right" ) );
  }
  return dest;
}

wxString wxString::AfterLast( wxChar ch ) const {
  wxString str;
  int iPos = Find( ch, true );
  if( iPos == wxNOT_FOUND ) {
    str = *this;
  } else
  { str = c_str() + iPos + 1; }
  return str;
}

wxString wxString::Left( size_t nCount ) const {
  if( nCount > length() ) {
    nCount = length();
  }
  wxString dest( *this, 0, nCount );
  if( dest.length() != nCount ) {
    wxFAIL_MSG( _T( "out of memory in wxString::Left" ) );
  }
  return dest;
}

wxString wxString::BeforeFirst( wxChar ch ) const {
  int iPos = Find( ch );
  if( iPos == wxNOT_FOUND ) {
    iPos = length();
  }
  return wxString( *this, 0, iPos );
}

wxString wxString::BeforeLast( wxChar ch ) const {
  wxString str;
  int iPos = Find( ch, true );
  if( iPos != wxNOT_FOUND && iPos != 0 ) {
    str = wxString( c_str(), iPos );
  }
  return str;
}

wxString wxString::AfterFirst( wxChar ch ) const {
  wxString str;
  int iPos = Find( ch );
  if( iPos != wxNOT_FOUND ) {
    str = c_str() + iPos + 1;
  }
  return str;
}

size_t wxString::Replace( const wxChar *szOld, const wxChar *szNew, bool bReplaceAll ) {
  wxCHECK_MSG( szOld && *szOld && szNew, 0,
               _T( "wxString::Replace(): invalid parameter" ) );
  size_t uiCount = 0;
  if( szOld[1] == '\0' && ( szNew[0] != '\0' && szNew[1] == '\0' ) ) {
    for( size_t pos = 0; ; ) {
      pos = find( *szOld, pos );
      if( pos == npos ) {
        break;
      }
      ( *this )[pos++] = *szNew;
      uiCount++;
      if( !bReplaceAll ) {
        break;
      }
    }
  } else {
    const size_t uiOldLen = wxStrlen( szOld );
    const size_t uiNewLen = wxStrlen( szNew );
    for( size_t pos = 0; ; ) {
      pos = find( szOld, pos );
      if( pos == npos ) {
        break;
      }
      replace( pos, uiOldLen, szNew, uiNewLen );
      pos += uiNewLen;
      uiCount++;
      if( !bReplaceAll ) {
        break;
      }
    }
  }
  return uiCount;
}

bool wxString::IsAscii() const {
  const wxChar *s = ( const wxChar* ) *this;
  while( *s ) {
    if( !isascii( *s ) ) {
      return( false );
    }
    s++;
  }
  return( true );
}

bool wxString::IsWord() const {
  const wxChar *s = ( const wxChar* ) *this;
  while( *s ) {
    if( !wxIsalpha( *s ) ) {
      return( false );
    }
    s++;
  }
  return( true );
}

bool wxString::IsNumber() const {
  const wxChar *s = ( const wxChar* ) *this;
  if( wxStrlen( s ) )
    if( ( s[0] == wxT( '-' ) ) || ( s[0] == wxT( '+' ) ) ) {
      s++;
    }
  while( *s ) {
    if( !wxIsdigit( *s ) ) {
      return( false );
    }
    s++;
  }
  return( true );
}

wxString wxString::Strip( stripType w ) const {
  wxString s = *this;
  if( w & leading ) {
    s.Trim( false );
  }
  if( w & trailing ) {
    s.Trim( true );
  }
  return s;
}

wxString& wxString::MakeUpper() {
  for( iterator it = begin(), en = end(); it != en; ++it ) {
    *it = ( wxChar )wxToupper( *it );
  }
  return *this;
}

wxString& wxString::MakeLower() {
  for( iterator it = begin(), en = end(); it != en; ++it ) {
    *it = ( wxChar )wxTolower( *it );
  }
  return *this;
}

inline int wxSafeIsspace( wxChar ch ) { return ( ch < 127 ) && wxIsspace( ch ); }

wxString& wxString::Trim( bool bFromRight ) {
  if( !empty() &&
      (
        ( bFromRight && wxSafeIsspace( GetChar( length() - 1 ) ) ) ||
        ( !bFromRight && wxSafeIsspace( GetChar( 0u ) ) )
      )
    ) {
    if( bFromRight ) {
      reverse_iterator psz = rbegin();
      while( ( psz != rend() ) && wxSafeIsspace( *psz ) ) {
        psz++;
      }
      erase( psz.base(), end() );
    } else {
      iterator psz = begin();
      while( ( psz != end() ) && wxSafeIsspace( *psz ) ) {
        psz++;
      }
      erase( begin(), psz );
    }
  }
  return *this;
}

wxString& wxString::Pad( size_t nCount, wxChar chPad, bool bFromRight ) {
  wxString s( chPad, nCount );
  if( bFromRight ) {
    *this += s;
  } else {
    s += *this;
    swap( s );
  }
  return *this;
}

wxString& wxString::Truncate( size_t uiLen ) {
  if( uiLen < length() ) {
    erase( begin() + uiLen, end() );
  }
  return *this;
}

int wxString::Find( wxChar ch, bool bFromEnd ) const {
  size_type idx = bFromEnd ? find_last_of( ch ) : find_first_of( ch );
  return ( idx == npos ) ? wxNOT_FOUND : ( int )idx;
}

int wxString::Find( const wxChar *pszSub ) const {
  size_type idx = find( pszSub );
  return ( idx == npos ) ? wxNOT_FOUND : ( int )idx;
}

template <typename T, typename F>
bool wxStringToIntType( const wxChar *start,
                        T *val,
                        int base,
                        F func ) {
  wxCHECK_MSG( val, false, _T( "NULL output pointer" ) );
  wxASSERT_MSG( !base || ( base > 1 && base <= 36 ), _T( "invalid base" ) );
  errno = 0;
  wxChar *end;
  *val = ( *func )( start, &end, base );
  return !*end && ( end != start ) && ( errno != ERANGE )         ;
}

bool wxString::ToLong( long *val, int base ) const {
  return wxStringToIntType( c_str(), val, base, wxStrtol );
}

bool wxString::ToULong( unsigned long *val, int base ) const {
  return wxStringToIntType( c_str(), val, base, wxStrtoul );
}

bool wxString::ToLongLong( wxLongLong_t *val, int base ) const {
  #ifdef wxHAS_STRTOLL
  return wxStringToIntType( c_str(), val, base, wxStrtoll );
  #else
  wxUnusedVar( val );
  wxUnusedVar( base );
  return false;
  #endif
}

bool wxString::ToULongLong( wxULongLong_t *val, int base ) const {
  #ifdef wxHAS_STRTOLL
  return wxStringToIntType( c_str(), val, base, wxStrtoull );
  #else
  wxUnusedVar( val );
  wxUnusedVar( base );
  return false;
  #endif
}

bool wxString::ToDouble( double *val ) const {
  wxCHECK_MSG( val, false, _T( "NULL pointer in wxString::ToDouble" ) );
  errno = 0;
  const wxChar *start = c_str();
  wxChar *end;
  *val = wxStrtod( start, &end );
  return !*end && ( end != start ) && ( errno != ERANGE ) ;
}

wxString wxString::Format( const wxChar *pszFormat, ... ) {
  va_list argptr;
  va_start( argptr, pszFormat );
  wxString s;
  s.PrintfV( pszFormat, argptr );
  va_end( argptr );
  return s;
}

wxString wxString::FormatV( const wxChar *pszFormat, va_list argptr ) {
  wxString s;
  s.PrintfV( pszFormat, argptr );
  return s;
}

int wxString::Printf( const wxChar *pszFormat, ... ) {
  va_list argptr;
  va_start( argptr, pszFormat );
  int iLen = PrintfV( pszFormat, argptr );
  va_end( argptr );
  return iLen;
}

int wxString::PrintfV( const wxChar* pszFormat, va_list argptr ) {
  int size = 1024;
  for( ;; ) {
    wxStringBuffer tmp( *this, size + 1 );
    wxChar *buf = tmp;
    if( !buf ) {
      return -1;
    }
    va_list argptrcopy;
    wxVaCopy( argptrcopy, argptr );
    errno = 0;
    int len = wxVsnprintf( buf, size, pszFormat, argptrcopy );
    va_end( argptrcopy );
    buf[size] = _T( '\0' );
    if( len < 0 ) {
      #if wxUSE_WXVSNPRINTF
      return -1;
      #else
      #if !defined(__WXWINCE__) && (!defined(__OS2__) || defined(__INNOTEK_LIBC__))
      if( ( errno == EILSEQ ) || ( errno == EINVAL ) ) {
        return -1;
      } else
      #endif // __WXWINCE__
        size *= 2;
      #endif
    } else if( len >= size ) {
      #if wxUSE_WXVSNPRINTF
      size *= 2;
      #else
      size = len + 1;
      #endif
    } else {
      break;
    }
  }
  Shrink();
  return length();
}

bool wxString::Matches( const wxChar *pszMask ) const {
  const wxChar *pszTxt = c_str();
  const wxChar *pszLastStarInText = NULL;
  const wxChar *pszLastStarInMask = NULL;
match:
  for( ; *pszMask != wxT( '\0' ); pszMask++, pszTxt++ ) {
    switch( *pszMask ) {
      case wxT( '?' ):
        if( *pszTxt == wxT( '\0' ) ) {
          return false;
        }
        break;
      case wxT( '*' ): {
        pszLastStarInText = pszTxt;
        pszLastStarInMask = pszMask;
        while( *pszMask == wxT( '*' ) || *pszMask == wxT( '?' ) ) {
          pszMask++;
        }
        if( *pszMask == wxT( '\0' ) ) {
          return true;
        }
        size_t uiLenMask;
        const wxChar *pEndMask = wxStrpbrk( pszMask, wxT( "*?" ) );
        if( pEndMask != NULL ) {
          uiLenMask = pEndMask - pszMask;
        } else {
          uiLenMask = wxStrlen( pszMask );
        }
        wxString strToMatch( pszMask, uiLenMask );
        const wxChar* pMatch = wxStrstr( pszTxt, strToMatch );
        if( pMatch == NULL ) {
          return false;
        }
        pszTxt = pMatch + uiLenMask - 1;
        pszMask += uiLenMask - 1;
      }
      break;
      default:
        if( *pszMask != *pszTxt ) {
          return false;
        }
        break;
    }
  }
  if( *pszTxt == wxT( '\0' ) ) {
    return true;
  }
  if( pszLastStarInText ) {
    pszTxt = pszLastStarInText + 1;
    pszMask = pszLastStarInMask;
    pszLastStarInText = NULL;
    goto match;
  }
  return false;
}

int wxString::Freq( wxChar ch ) const {
  int count = 0;
  int len = length();
  for( int i = 0; i < len; i++ ) {
    if( GetChar( i ) == ch ) {
      count ++;
    }
  }
  return count;
}

wxString wxString::Upper() const {
  wxString s( *this );
  return s.MakeUpper();
}

wxString wxString::Lower() const {
  wxString s( *this );
  return s.MakeLower();
}

int wxString::sprintf( const wxChar *pszFormat, ... ) {
  va_list argptr;
  va_start( argptr, pszFormat );
  int iLen = PrintfV( pszFormat, argptr );
  va_end( argptr );
  return iLen;
}

#include "wx/arrstr.h"

wxArrayString::wxArrayString( size_t sz, const wxChar** a ) {
  #if !wxUSE_STL
  Init( false );
  #endif
  for( size_t i = 0; i < sz; i++ ) {
    Add( a[i] );
  }
}

wxArrayString::wxArrayString( size_t sz, const wxString* a ) {
  #if !wxUSE_STL
  Init( false );
  #endif
  for( size_t i = 0; i < sz; i++ ) {
    Add( a[i] );
  }
}

#if !wxUSE_STL

// size increment = min(50% of current size, ARRAY_MAXSIZE_INCREMENT)
#define   ARRAY_MAXSIZE_INCREMENT       4096

#ifndef   ARRAY_DEFAULT_INITIAL_SIZE    // also defined in dynarray.h
#define   ARRAY_DEFAULT_INITIAL_SIZE    (16)
#endif

#define   STRING(p)   ((wxString *)(&(p)))

// ctor
void wxArrayString::Init( bool autoSort ) {
  m_nSize  =
    m_nCount = 0;
  m_pItems = ( wxChar ** ) NULL;
  m_autoSort = autoSort;
}

// copy ctor
wxArrayString::wxArrayString( const wxArrayString& src ) {
  Init( src.m_autoSort );
  *this = src;
}

// assignment operator
wxArrayString& wxArrayString::operator=( const wxArrayString& src ) {
  if( m_nSize > 0 ) {
    Clear();
  }
  Copy( src );
  m_autoSort = src.m_autoSort;
  return *this;
}

void wxArrayString::Copy( const wxArrayString& src ) {
  if( src.m_nCount > ARRAY_DEFAULT_INITIAL_SIZE ) {
    Alloc( src.m_nCount );
  }
  for( size_t n = 0; n < src.m_nCount; n++ ) {
    Add( src[n] );
  }
}

// grow the array
void wxArrayString::Grow( size_t nIncrement ) {
  // only do it if no more place
  if( ( m_nSize - m_nCount ) < nIncrement ) {
    // if ARRAY_DEFAULT_INITIAL_SIZE were set to 0, the initially empty would
    // be never resized!
    #if ARRAY_DEFAULT_INITIAL_SIZE == 0
#error "ARRAY_DEFAULT_INITIAL_SIZE must be > 0!"
    #endif
    if( m_nSize == 0 ) {
      // was empty, alloc some memory
      m_nSize = ARRAY_DEFAULT_INITIAL_SIZE;
      if( m_nSize < nIncrement ) {
        m_nSize = nIncrement;
      }
      m_pItems = new wxChar *[m_nSize];
    } else {
      // otherwise when it's called for the first time, nIncrement would be 0
      // and the array would never be expanded
      // add 50% but not too much
      size_t ndefIncrement = m_nSize < ARRAY_DEFAULT_INITIAL_SIZE
                             ? ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
      if( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) {
        ndefIncrement = ARRAY_MAXSIZE_INCREMENT;
      }
      if( nIncrement < ndefIncrement ) {
        nIncrement = ndefIncrement;
      }
      m_nSize += nIncrement;
      wxChar **pNew = new wxChar *[m_nSize];
      // copy data to new location
      memcpy( pNew, m_pItems, m_nCount * sizeof( wxChar * ) );
      // delete old memory (but do not release the strings!)
      wxDELETEA( m_pItems );
      m_pItems = pNew;
    }
  }
}

void wxArrayString::Free() {
  for( size_t n = 0; n < m_nCount; n++ ) {
    STRING( m_pItems[n] )->GetStringData()->Unlock();
  }
}

// deletes all the strings from the list
void wxArrayString::Empty() {
  Free();
  m_nCount = 0;
}

// as Empty, but also frees memory
void wxArrayString::Clear() {
  Free();
  m_nSize  =
    m_nCount = 0;
  wxDELETEA( m_pItems );
}

// dtor
wxArrayString::~wxArrayString() {
  Free();
  wxDELETEA( m_pItems );
}

void wxArrayString::reserve( size_t nSize ) {
  Alloc( nSize );
}

// pre-allocates memory (frees the previous data!)
void wxArrayString::Alloc( size_t nSize ) {
  // only if old buffer was not big enough
  if( nSize > m_nSize ) {
    wxChar **pNew = new wxChar *[nSize];
    if( !pNew ) {
      return;
    }
    memcpy( pNew, m_pItems, m_nCount * sizeof( wxChar * ) );
    delete [] m_pItems;
    m_pItems = pNew;
    m_nSize  = nSize;
  }
}

// minimizes the memory usage by freeing unused memory
void wxArrayString::Shrink() {
  // only do it if we have some memory to free
  if( m_nCount < m_nSize ) {
    // allocates exactly as much memory as we need
    wxChar **pNew = new wxChar *[m_nCount];
    // copy data to new location
    memcpy( pNew, m_pItems, m_nCount * sizeof( wxChar * ) );
    delete [] m_pItems;
    m_pItems = pNew;
    m_nSize = m_nCount;
  }
}

// searches the array for an item (forward or backwards)
int wxArrayString::Index( const wxChar *sz, bool bCase, bool bFromEnd ) const {
  if( m_autoSort ) {
    // use binary search in the sorted array
    wxASSERT_MSG( bCase && !bFromEnd,
                  wxT( "search parameters ignored for auto sorted array" ) );
    size_t i,
           lo = 0,
           hi = m_nCount;
    int res;
    while( lo < hi ) {
      i = ( lo + hi ) / 2;
      res = wxStrcmp( sz, m_pItems[i] );
      if( res < 0 ) {
        hi = i;
      } else if( res > 0 ) {
        lo = i + 1;
      } else
      { return i; }
    }
    return wxNOT_FOUND;
  } else {
    // use linear search in unsorted array
    if( bFromEnd ) {
      if( m_nCount > 0 ) {
        size_t ui = m_nCount;
        do {
          if( STRING( m_pItems[--ui] )->IsSameAs( sz, bCase ) ) {
            return ui;
          }
        } while( ui != 0 );
      }
    } else {
      for( size_t ui = 0; ui < m_nCount; ui++ ) {
        if( STRING( m_pItems[ui] )->IsSameAs( sz, bCase ) ) {
          return ui;
        }
      }
    }
  }
  return wxNOT_FOUND;
}

// add item at the end
size_t wxArrayString::Add( const wxString& str, size_t nInsert ) {
  if( m_autoSort ) {
    // insert the string at the correct position to keep the array sorted
    size_t i,
           lo = 0,
           hi = m_nCount;
    int res;
    while( lo < hi ) {
      i = ( lo + hi ) / 2;
      res = str.Cmp( m_pItems[i] );
      if( res < 0 ) {
        hi = i;
      } else if( res > 0 ) {
        lo = i + 1;
      } else {
        lo = hi = i;
        break;
      }
    }
    wxASSERT_MSG( lo == hi, wxT( "binary search broken" ) );
    Insert( str, lo, nInsert );
    return ( size_t )lo;
  } else {
    wxASSERT( str.GetStringData()->IsValid() );
    Grow( nInsert );
    for( size_t i = 0; i < nInsert; i++ ) {
      // the string data must not be deleted!
      str.GetStringData()->Lock();
      // just append
      m_pItems[m_nCount + i] = ( wxChar * )str.c_str(); // const_cast
    }
    size_t ret = m_nCount;
    m_nCount += nInsert;
    return ret;
  }
}

// add item at the given position
void wxArrayString::Insert( const wxString& str, size_t nIndex, size_t nInsert ) {
  wxASSERT( str.GetStringData()->IsValid() );
  wxCHECK_RET( nIndex <= m_nCount, wxT( "bad index in wxArrayString::Insert" ) );
  wxCHECK_RET( m_nCount <= m_nCount + nInsert,
               wxT( "array size overflow in wxArrayString::Insert" ) );
  Grow( nInsert );
  memmove( &m_pItems[nIndex + nInsert], &m_pItems[nIndex],
           ( m_nCount - nIndex )*sizeof( wxChar * ) );
  for( size_t i = 0; i < nInsert; i++ ) {
    str.GetStringData()->Lock();
    m_pItems[nIndex + i] = ( wxChar * )str.c_str();
  }
  m_nCount += nInsert;
}

// range insert (STL 23.2.4.3)
void
wxArrayString::insert( iterator it, const_iterator first, const_iterator last ) {
  const int idx = it - begin();
  // grow it once
  Grow( last - first );
  // reset "it" since it can change inside Grow()
  it = begin() + idx;
  while( first != last ) {
    it = insert( it, *first );
    // insert returns an iterator to the last element inserted but we need
    // insert the next after this one, that is before the next one
    ++it;
    ++first;
  }
}

// expand the array
void wxArrayString::SetCount( size_t count ) {
  Alloc( count );
  wxString s;
  while( m_nCount < count ) {
    m_pItems[m_nCount++] = ( wxChar * )s.c_str();
  }
}

// removes item from array (by index)
void wxArrayString::RemoveAt( size_t nIndex, size_t nRemove ) {
  wxCHECK_RET( nIndex < m_nCount, wxT( "bad index in wxArrayString::Remove" ) );
  wxCHECK_RET( nIndex + nRemove <= m_nCount,
               wxT( "removing too many elements in wxArrayString::Remove" ) );
  // release our lock
  for( size_t i = 0; i < nRemove; i++ ) {
    Item( nIndex + i ).GetStringData()->Unlock();
  }
  memmove( &m_pItems[nIndex], &m_pItems[nIndex + nRemove],
           ( m_nCount - nIndex - nRemove )*sizeof( wxChar * ) );
  m_nCount -= nRemove;
}

// removes item from array (by value)
void wxArrayString::Remove( const wxChar *sz ) {
  int iIndex = Index( sz );
  wxCHECK_RET( iIndex != wxNOT_FOUND,
               wxT( "removing inexistent element in wxArrayString::Remove" ) );
  RemoveAt( iIndex );
}

void wxArrayString::assign( const_iterator first, const_iterator last ) {
  reserve( last - first );
  for( ; first != last; ++first ) {
    push_back( *first );
  }
}

// ----------------------------------------------------------------------------
// sorting
// ----------------------------------------------------------------------------

// we can only sort one array at a time with the quick-sort based
// implementation
#if wxUSE_THREADS
// need a critical section to protect access to gs_compareFunction and
// gs_sortAscending variables
static wxCriticalSection gs_critsectStringSort;
#endif // wxUSE_THREADS

// function to use for string comparaison
static wxArrayString::CompareFunction gs_compareFunction = NULL;

// if we don't use the compare function, this flag tells us if we sort the
// array in ascending or descending order
static bool gs_sortAscending = true;

// function which is called by quick sort
extern "C" int wxC_CALLING_CONV     // LINKAGEMODE
wxStringCompareFunction( const void *first, const void *second ) {
  wxString *strFirst = ( wxString * )first;
  wxString *strSecond = ( wxString * )second;
  if( gs_compareFunction ) {
    return gs_compareFunction( *strFirst, *strSecond );
  } else {
    // maybe we should use wxStrcoll
    int result = strFirst->Cmp( *strSecond );
    return gs_sortAscending ? result : -result;
  }
}

// sort array elements using passed comparaison function
void wxArrayString::Sort( CompareFunction compareFunction ) {
  wxCRIT_SECT_LOCKER( lockCmpFunc, gs_critsectStringSort );
  wxASSERT( !gs_compareFunction );  // must have been reset to NULL
  gs_compareFunction = compareFunction;
  DoSort();
  // reset it to NULL so that Sort(bool) will work the next time
  gs_compareFunction = NULL;
}

extern "C"
{
  typedef int ( wxC_CALLING_CONV * wxStringCompareFn )( const void *first,
      const void *second );
}

void wxArrayString::Sort( CompareFunction2 compareFunction ) {
  qsort( m_pItems, m_nCount, sizeof( wxChar * ), ( wxStringCompareFn )compareFunction );
}

void wxArrayString::Sort( bool reverseOrder ) {
  Sort( reverseOrder ? wxStringSortDescending : wxStringSortAscending );
}

void wxArrayString::DoSort() {
  wxCHECK_RET( !m_autoSort, wxT( "can't use this method with sorted arrays" ) );
  // just sort the pointers using qsort() - of course it only works because
  // wxString() *is* a pointer to its data
  qsort( m_pItems, m_nCount, sizeof( wxChar * ), wxStringCompareFunction );
}

bool wxArrayString::operator==( const wxArrayString& a ) const {
  if( m_nCount != a.m_nCount ) {
    return false;
  }
  for( size_t n = 0; n < m_nCount; n++ ) {
    if( Item( n ) != a[n] ) {
      return false;
    }
  }
  return true;
}

#endif // !wxUSE_STL

int wxCMPFUNC_CONV wxStringSortAscending( wxString* s1, wxString* s2 ) {
  return  s1->Cmp( *s2 );
}

int wxCMPFUNC_CONV wxStringSortDescending( wxString* s1, wxString* s2 ) {
  return -s1->Cmp( *s2 );
}

wxString* wxCArrayString::Release() {
  wxString *r = GetStrings();
  m_strings = NULL;
  return r;
}
